package com.lfg.leetcode.leetcode200;

public class No264nthUglyNumber {

    public static void main(String[] args) {
        int ret = nthUglyNumber(10);
        System.out.println(ret);
    }

    public static int nthUglyNumber(int n) {
        int[] dp = new int[n];
        int i2 = 0;
        int i3 = 0;
        int i5 = 0;

        int index = 1;
        dp[0] = 1;
        while (index < n) {
            int d2 = dp[i2] * 2;
            int d3 = dp[i3] * 3;
            int d5 = dp[i5] * 5;
            int data = Math.min(Math.min(d2, d3), d5);
            if (data == d2) {
                i2++;
            }
            if (data == d3) {
                i3++;
            }
            if (data == d5) {
                i5++;
            }
            dp[index++] = data;
        }
        return dp[n - 1];
    }


}
